package com.ttx.algorithm.leetcode.traversal;

import java.util.HashSet;

/**
 * https://leetcode-cn.com/problems/number-of-islands/
 * 200 岛屿数量  <br>
 *
 * <p>
 *     给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
 *     一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
 *     你可以假设网格的四个边均被水包围。
 *
 *    输入:
 *    11000
 *    11000
 *    00100
 *    00011
 *
 *    输出: 3
 *
 * </p>
 *
 * @author TimFruit
 * @date 19-10-1 下午11:12
 */
public class P200NumberOfIslands3 {

    // https://www.jianshu.com/p/89cea54d3f22
    // 使用并查集实现
    public int numIslands(char[][] grid) {

        if(grid==null || grid.length==0){
            return 0;
        }
        int rows=grid.length;
        int len=grid[0].length;

        int num=0;//岛屿个数

        int max=rows*len+1;
        int[] parent=new int[max];  //父节点
        int[] rank=new int[max]; //高度



        init(parent, rank);

        for(int i=0; i<rows; i++){
            for(int j=0; j<len; j++){

                if(grid[i][j]=='0'){
                    continue;
                }

                // 上
                if(i-1>=0 && grid[i-1][j]=='1' ){
                    merge(parent, rank, i, j, i-1, j, len);
                }
                // 下
                if(i+1<rows  && grid[i+1][j]=='1' ){
                    merge(parent, rank, i, j, i+1, j, len);
                }
                // 左
                if(j-1>=0 && grid[i][j-1]=='1' ){
                    merge(parent, rank, i, j, i, j-1, len);
                }
                // 右
                if(j+1<len && grid[i][j+1]=='1' ){
                    merge(parent, rank, i, j, i, j+1, len);
                }
            }
        }


        // warning 可以在刚开始初始化时记录 值为1的个数, 然后每真实合并一次,减1
        // 查找不一样的根
        HashSet<Integer> roots=new HashSet<Integer>();
        int root;
        for(int i=0; i<rows; i++){
            for(int j=0; j<len; j++){
                if(grid[i][j]=='0'){
                    continue;
                }
                root=findRoot(parent, i, j, len);
                roots.add(root);
            }
        }

        return roots.size();
    }



    // ===============================
    // 以下是二维坐标与并查集坐标的转换
    // ===============================

    // 获取坐标为[i,j]的并查集中的下标
    private int getSubIndex(int i, int j, int len){
        return i*len+j;
    }


    private int findRoot(int[] parent, int i, int j,int len){
        int rootIndex=getSubIndex(i,j, len);
        return findRoot(parent, rootIndex);
    }



    private void merge(int[] parent, int[] rank, int i, int j, int i2, int j2, int len){
        int root1=findRoot(parent, i, j, len);
        int root2=findRoot(parent, i2, j2, len);


        merge(parent, rank, root1, root2);
    }



    // ================================
    // 以下是并查集的标准实现
    // ================================


    private void init(int[] parent, int[] rank){
        for(int i=0,size=parent.length; i<size; i++){
            parent[i]=i;
//            rank[i]=0; //可以省略
        }
    }


    private int findRoot(int[] parent, int sub){
        if(sub>parent.length){
            throw new IllegalArgumentException("子节点值超过父节点数组下表");
        }
        while(parent[sub]!=sub){
            sub=parent[sub];
        }
        return sub;
    }



    private void merge(int[] parent, int[] rank, int root1, int root2){
        if(root1==root2){
            return;
        }

        if(rank[root1]>rank[root2]){
            // root2 --> 合并到 root1
            parent[root2]=root1;
        }else if(rank[root1]<rank[root2]){
            // root1 --> 合并到 root2
            parent[root1]=root2;
        }else {
            // root2 --> 合并到 root1
            parent[root2]=root1;
            rank[root1]++;
        }
    }











}
